/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        //先得到链表的长度，再倒序插入数组中
        //时间复杂度O(n + n)，空间复杂度O(n)

        vector<int> reversed;
		int count = 0;  //存储链表的长度

        if(head == NULL) return reversed;  //空链表

        ListNode *head_start = head;  //链表头地址
        while(head != NULL){
            count++;
            head = head->next;
        }

        reversed.resize(count);  //调整数组长度
        head = head_start;

        for(int i = count - 1; i >= 0; --i){
            reversed[i] = head->val;
            head = head->next;
        }

        return reversed;
    }
};